#include <cstring>

void _MergeSort(int* arr, int* tmp, int left, int right)
{
    if (left >= right)
        return;
    int mid = left + (right - left) / 2;
    int begin1 = left, end1 = mid;
    int begin2 = mid + 1, end2 = right;

    _MergeSort(arr, tmp, begin1, end1);
    _MergeSort(arr, tmp, begin2, end2);

    int i = begin1; //为拷贝到tmp数组中准备的，更改tmp数组内容的索引
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (arr[begin1] <= arr[begin2])
        {
            tmp[i++] = arr[begin1++];
        }
        else
        {
            tmp[i++] = arr[begin2++];
        }
    }
    while (begin1 <= end1)
    {
        tmp[i++] = arr[begin1++];
    }
    while (begin2 <= end2)
    {
        tmp[i++] = arr[begin2++];
    }

    //将tmp的内容拷贝到原数组arr中
    //写法1：遍历赋值
    /*for (int i = left;i <= right; ++i)
    {
        arr[i] = tmp[i];
    }*/

    //写法二：使用memcpy函数
    memcpy(arr + left, tmp + left, sizeof(int) * (right - left + 1));
}

void MergeSort(int* arr, int size)
{
    int* tmp = new int[size]();//创建一个临时数组
    int left = 0, right = size - 1;
    _MergeSort(arr, tmp, left, right);
    delete[] tmp;
    return;
}